package bintree.LeetCode;
//958. 二叉树的完全性检验

/**
 * 给定一个二叉树的 root ，确定它是否是一个 完全二叉树
 */

import java.util.Deque;
import java.util.LinkedList;

/**
 * 思路：用层序遍历的思修解决，队列。将判断完全二叉树分为两个阶段。
 * 第—阶段:在该阶段下，每个节点都有左右子树
 * 当碰到第一个只有左子树没有右子树的节点 或者 第一个叶子节点， 就切换状态，进入第二阶段。（用标记位切换）
 * 如果当碰到一个节点只有右树没有左树，反例，直接return false。
 * 第二阶段:在该阶段下，每个节点都是叶子结点，若在第二阶段下发现了有节点有子树，反例，直接return false。
 */
public class Num958_isCompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //判断是否为第二阶段，标志位
        boolean isSecondstep = false;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(isSecondstep == false){
                //进入第一阶段
                //第一阶段节点必须要有左右子树
                if(node.left != null && node.right != null){
                    //把左右子树入队列
                    queue.offer(node.left);
                    queue.offer(node.right);
                }else if(node.left == null && node.right != null){
                    //此时是左子树为空，存在右子树,反例
                    return false;
                }else if(node.right == null && node.left != null){
                    //此时是右子树为空，存在左子树，装备进入第二阶段
                    isSecondstep = true;
                    //把存在的左子树入队列
                    queue.offer(node.left);
                }else{
                    //碰到了叶子节点，直接转节点
                    isSecondstep = true;
                }

            }else{
                //进入第二阶段
                if(node.right != null || node.left != null){
                    //居然不是叶子节点，妥妥的反例。
                    return false;
                }
            }
        }
        return true;
    }
}
